#include <cstddef>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) {
	if(*pi >= n) {
		return NULL;
	}
	BTDataType temp = a[*pi];
	(*pi)++;
	if(temp == '#') {
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->_data = temp;
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root) {
	if(*root == NULL) {
		return;
	}
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
	*root = NULL;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root) {
	if(root == NULL) {
		return 0;
	}
	int l = BinaryTreeSize(root->_left);
	int r = BinaryTreeSize(root->_right);
	return l + r + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) {
	if(root == NULL) {
		return 0;
	}
	if(root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {
	if(k < 0 || (k > 0 && root == NULL)) {
		return 0;
	}
	if(k == 1) {
		return root != NULL ? 1 : 0;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if(root == NULL) {
		return NULL;
	}
	if(root->_data == x) {
		return root;
	}
	BTNode* l = BinaryTreeFind(root->_left, x);
	BTNode* r = BinaryTreeFind(root->_right, x);
	if(l != NULL) {
		return l;
	}else {
		return r;
	}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root) {
	if(root == NULL) {
		return ;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) {
	if(root == NULL) {
		return ;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) {
	if(root == NULL) {
		return ;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root) {
	if(root == NULL) {
		return;
	}
	std::queue<BTNode*> a;
	a.push(root);
	while(!a.empty()) {
		BTNode* temp = a.front();
		a.pop();
		printf("%c ", temp->_data);
		if(temp->_left != NULL) {
			a.push(temp->_left);
		}
		if(temp->_right != NULL) {
			a.push(temp->_right);
		}
	}
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) 
{
	int flag = 0;
	std::queue<BTNode*> a;
	a.push(root);
	while(!a.empty()) {
		BTNode* temp = a.front();
		if(temp == NULL) {
			if(!flag)
			{
				flag = 1;
				a.pop();
				continue;
			}
		}else {
			if(flag) {
				return 0;
			}
		}
		a.pop();
		if(temp != NULL) {
			a.push(temp->_left);
			a.push(temp->_right);
		}
		
	}
	return 1;
}
int length(BTNode* root) {
	if(root == NULL) {
		return 0;
	}
	return length(root->_left) 
}
int main() {
	char *s = "ABD##E#H##CF##G##";
	// char *s = "ABD##E##CF##G##";
	int i = 0;
	BTNode* node = BinaryTreeCreate(s, strlen(s), &i);
	// int temp = BinaryTreeSize(node);
	// printf("%d\n", temp);
	// int temp = BinaryTreeLeafSize(node);
	// int temp = BinaryTreeLevelKSize(node, 4);
	// printf("%d\n", temp);
	// BTNode* temp = BinaryTreeFind(node, 'G');
	// if(temp == NULL) {
	// 	printf("not find");
	// }
	// printf("%c\n", temp->_data);
	// BinaryTreePrevOrder(node);
	// BinaryTreeInOrder(node);
	// BinaryTreePostOrder(node);
	// BinaryTreeLevelOrder(node);
	printf("%d\n", BinaryTreeComplete(node));

    return 0;
}